The secure search is a technology that performs searching of encrypted data remaining encrypted.
In recent years, as to managing data on the Internet such as cloud services, there has been attention focused on the secure search as a security technology to protect secret information even from eavesdropping by a server administrator.
There are two types of the method for realizing the secure search: the method of using deterministic encryption and the method of using probabilistic encryption.
The deterministic encryption is an encryption scheme being characterized in that, when encrypting the same keyword, the same ciphertext is obtained even how many times the keyword is repeatedly encrypted.
Therefore, it has a feature in that searching can be performed speedily by using the high-speed method realized in the conventional database.
On the other hand, it has a disadvantage in that since frequency of appearance of encrypted data can be counted, for example, when a keyword is a family name, the content of the encrypted data will be able to be inferred based on information on population ratio regarding family names generally known, and the like (for example, Non-Patent Literature 2).
By contrast, the probabilistic encryption is an encryption scheme being characterized in that, even in the case of encrypting the same keyword, a different ciphertext is generated at every encryption.
Therefore, it has a feature of high security because whether keywords are the same or not is unknown even if encrypted data are simply compared with each other and thus, inferring the keyword by counting the frequency of appearance, which is a problem of the deterministic encryption, cannot be performed.
On the other hand, since even the identity of keywords is unknown, the high-speed method realized in the conventional database cannot be used, thereby having a disadvantage in that search is slow (for example, Non-Patent Literatures 1, 3, 4, and 5).
As a method of accelerating the secure search using the probabilistic encryption, there is proposed an idea of shortening the average response time by caching search results.
This is based on focusing an attention on a feature that a general search may be performed twice or more using the same keyword, and then, this aims to accelerate searching by, though the first search takes time, caching its result and merely returning the cached result at the second and subsequent search (for example, Patent Literature 1).